package leetcode.code0990;

import java.util.HashMap;
import java.util.Map;

public class Solution2 {

	Map<Integer, Integer> p;

	public void init() {
		p = new HashMap<>();
	}

	public void union(int a, int b) {
		p.put(find(a), find(b));
	}

	public int find(int id) {
		if (!p.containsKey(id)) {
			p.put(id, id);
		}
		if (p.get(id) != id) {
			p.put(id, this.find(p.get(id)));
		}
		return p.get(id);
	}

	public boolean isSameSet(int a, int b) {
		return find(a) == find(b);
	}

	public boolean equationsPossible(String[] equations) {
		this.init();
		for (String equ : equations) {
			if (equ.charAt(1) == '=') {
				union(equ.charAt(0), equ.charAt(3));
			}
		}
		for (String equ : equations) {
			if (equ.charAt(1) == '!') {
				if (isSameSet(equ.charAt(0), equ.charAt(3))) {
					return false;
				}
			}
		}
		return true;
	}
}
